//
// Created by WuYong on 2021/12/20.
//

#include "Linear_DDCLinkList.h"

//与循环单链表思想类似，参看前面代码注释

Status ListInit(LinkList* L){
    ElemType* po= CreatElem(0);//初始化头节点的数据
    if(!po) exit(ERROR);
    LNode* head = (LNode*) malloc(sizeof(LNode));//初始化头节点数据
    if(!head) exit(ERROR);
    head->data=po;
    head->next=head;
    head->prior=head;
    L->head=head;//初始化链表
    L->tail=head;
    L->ListSize=0;

    return OK;
}

Status DestroyList(LinkList* L){
    if(L==NULL||L->head==NULL) return ERROR;

    ClearList(L);
    free(L->head);
    L->head=NULL;
    L->tail=NULL;
    free(L);
    L=NULL;
    return OK;
}

Status ClearList(LinkList* L){
    if(L==NULL||L->head==NULL) return ERROR;
    if(L->head->next==NULL) return OK;

    LNode * P = L->head->next;      //Modified
    LNode * Ptmp;
    int flag=0;     //Modified
    while (P!=L->head->next||!flag){    //Modified
        flag=1;
        Ptmp=P;
        P=P->next;
        free(Ptmp);
        Ptmp=NULL;
    }
    L->tail=L->head;
    L->tail->next=L->head;
    L->ListSize=0;

    return OK;
}

Status InsertFirst(LinkList* L,LNode s){
    if(L==NULL||L->head==NULL)    return ERROR;

    LNode * po=(LNode*) malloc(sizeof(LNode));
    if(!po) return ERROR;
    po->next=NULL;
    po->prior=NULL;
    po->data=s.data;

    L->head->next->prior=po;
    po->next=L->head->next;
    po->prior=L->tail;
    L->head->next=po;
    L->tail->next=L->head->next;//Modified
    L->ListSize++;

    return OK;
}

LNode DestroyFirst(LinkList* L){
    //留空给判断是否为空函数
    if(L==NULL||L->head->next==NULL||L->head==NULL) exit(ERROR);

    LNode* Ptmp=L->head->next;//保存要销毁的结点的地址
    LNode tmp;
    LNodeInit(&tmp);
    tmp.next=Ptmp->next;
    tmp.prior=Ptmp->prior;
    tmp.data=Ptmp->data;

    Ptmp->next->prior=L->tail;  //更新下一个节点的前驱指向
    L->tail->next=Ptmp->next;   //更新尾指针下一个指向
    L->head->next=Ptmp->next;   //将头节点的指向改变
    //原版
//    L->head->next->next->prior=L->tail;
//    L->head->next=L->head->next->next;
//    L->tail->next=L->head->next;

    free(Ptmp);
    Ptmp=NULL;
    L->ListSize--;

    return tmp;
}

Status Append(LinkList* LH,LinkList* LT){
    if(LH==NULL||LT==NULL||LH->head==NULL||LT->head==NULL)  return ERROR;

    LH->tail->next=LT->head->next;
    LT->tail->next=LH->head->next;      //Modified
    LT->head->next->prior=LH->tail;
    LH->tail=LT->tail;
    LH->head->next->prior=LH->tail;

    LH->ListSize+=LT->ListSize;
    return OK;
}

LNode RemoveTail(LinkList* L){
    if(L==NULL||L->head==NULL) exit(ERROR);

    LNode *Ptmp,re;
    LNodeInit(&re);
    Ptmp=L->tail;
    re.next=Ptmp->next;
    re.prior=Ptmp->prior;
    re.data=Ptmp->data;

//    LNode * tmp=L->head;
//    LNode * ptmp=L->tail;
//    while (tmp->next!=L->tail){
//        tmp=tmp->next;
//    }
    Ptmp->prior->next=Ptmp->next;   //Modified
    L->tail=Ptmp->prior;
    L->head->next->prior=Ptmp->prior;
    free(Ptmp);
    Ptmp=NULL;
    L->ListSize--;

    return re;
}

Status InsertBefore(LinkList* L,LNode* p,LNode s){
    if(L==NULL||L->head==NULL)  return ERROR;

    LNode * tmp=L->head;
    int flag=0;
    while ((tmp->next!=p&&tmp->next!=L->head->next)||!flag){     //Modified
        flag=1;
        tmp=tmp->next;
    }
    if(tmp->next==L->head->next) {
        printf("\np None Exist\n");
        return ERROR;
    }

    LNode * po=(LNode*) malloc(sizeof(LNode));
    if(!po) return ERROR;
    po->next=NULL;
    po->prior=NULL;
    po->data=s.data;

    po->next=tmp->next;
    po->prior=tmp;
    tmp->next->prior=po;
    tmp->next=po;
    if(tmp==L->head->next){     //Modified
        L->tail->next=po;
    }
    L->ListSize++;

    return OK;
}

Status InsertAfter(LinkList* L,LNode* p,LNode s){
    if(L==NULL||L->head==NULL)  return ERROR;


    LNode * tmp=L->head->next;
    int flag=0;
    while ((tmp!=p&&tmp!=L->head->next)||!flag){     //Modified
        flag=1;
        tmp=tmp->next;
    }
    if(tmp==NULL) {
        printf("\np none exist\n");
        return ERROR;
    }

    LNode * po=(LNode*) malloc(sizeof(LNode));
    if(!po) return ERROR;
    po->next=NULL;
    po->prior=NULL;
    po->data=s.data;

    po->next=tmp->next;
    po->prior=tmp;
    tmp->next->prior=po;
    tmp->next=po;



    L->ListSize++;

    return OK;
}

Status SetCurElem(LNode* p,ElemType e){
    *(p->data)=e;

    return OK;
}

ElemType GetCurElem(LNode p){
    return *p.data;
}

Status ListEmpty(LinkList L){
    if(L.head==NULL)    return ERROR;

    if(L.ListSize==0) return ERROR;
    else if(L.ListSize==1){
        return TRUE;
    } else
        return FALSE;
}

int ListLength(LinkList L){
    if(L.head== NULL)   return ERROR;

    return L.ListSize;
}

LNode* GetHead(LinkList L){
    if(L.head==NULL) exit(ERROR);
    return L.head->next;
}

LNode* GetLast(LinkList L){
    if(L.head==NULL) exit(ERROR);

    return L.tail;
}

LNode* PriorPos(LinkList L,LNode* p){
    if(L.head==NULL)    return NULL;
    if(p==L.head->next) return L.tail;

    LNode * tmp=L.head->next;
    while (tmp->next!=p&&tmp->next!=L.head->next){      //Modified
        tmp=tmp->next;
    }
    if(tmp==L.tail) return NULL;//若链表中没有此节点
    return tmp;
}

LNode* NextPos(LinkList L,LNode* p){
    if(L.head==NULL)    return NULL;
    if(p==L.tail)   return L.head->next;

    LNode * tmp=L.head->next;
    int flag=0;
    while ((tmp!=p&&tmp!=L.head->next)||!flag){      //Modified
        flag=1;
        tmp=tmp->next;
    }
    return tmp->next;
}

LNode* LocatePos(LinkList L,int i){
    if(L.head==NULL) exit(ERROR);

    if(i<1||i>L.ListSize){
        printf("\ni is illegal!(1<=i<=%d)\n", L.ListSize);
    }
    LNode * tmp=L.head->next;
    int j=1;
    while (j<i){
        tmp=tmp->next;
        j++;
    }

    return tmp;
}

LNode* LocateElem(LinkList L,ElemType e,Status (*compare)(ElemType,ElemType)){
    if(L.head==NULL)    return NULL;

    LNode * tmp=L.head->next;
    int flag=0;
    while (tmp!=L.head->next||!flag){      //Modified
        flag=1;
        if((*compare)(*tmp->data,e)){
            return tmp;
        }
        tmp=tmp->next;
    }
    return NULL;
}

Status ListTraverse(LinkList L,Status (*visit)(LNode* )){
    if(L.head==NULL||L.ListSize==0)    return ERROR;    //Modified

    LNode* tmp=L.head->next;
    if(tmp==NULL)
        return EMPTY;
    int flag=0;
    while (tmp!=L.head->next||!flag){      //Modified
        flag=1;
        (*visit)(tmp);
        tmp=tmp->next;
    }
    return OK;
}

Status ListInsert_L(LinkList* L,int i,LNode s){
    if(L==NULL||L->head==NULL) return ERROR;
    if(i<1||i>L->ListSize){
        printf("\nThe number is illegal!\n");
        return ERROR;
    }

    LNode* tmp=L->head;
    int j=0;
    while (j<i-1){
        tmp=tmp->next;
        j++;
    }

    LNode * po=(LNode*) malloc(sizeof(LNode));
    if(!po) return ERROR;
    po->next=NULL;
    po->prior=NULL;
    po->data=s.data;

    po->next=tmp->next;
    tmp->next->prior=po;
    tmp->next=po;
    if(tmp==L->head){
        po->prior=L->tail;
        L->tail->next=po;
    } else{
        po->prior=tmp;
    }


    return OK;
}

Status ListPushHead(LinkList* L,LNode s){
    if(L==NULL||L->head==NULL)  return ERROR;

    LNode * po=(LNode*) malloc(sizeof(LNode));
    if(!po) return ERROR;

    po->data=s.data;
    po->next=NULL;
    po->prior=NULL;

    if(L->head==L->tail){
        po->next=po;
        po->prior=po;
        L->head->next=po;
        L->tail=po;
    } else{
        po->next=L->head->next;
        po->prior=L->tail;
        L->head->next->prior=po;
        L->head->next=po;
        L->tail->next=po;
    }
    L->ListSize++;

    return OK;
}

Status LNodeInit(LNode* l){
    l=(LNode *)malloc(sizeof(LNode));
    l->next=NULL;
    l->prior=NULL;
    l->data= CreatElem(0);
    return OK;
}

ElemType* CreatElem(int data){
    ElemType* po=(ElemType*) malloc(sizeof(ElemType));
    *po=data;
    return po;

}


Status List_Sort(LinkList* L,Status (*compare)(ElemType e,ElemType f)){
    if(L==NULL||L->head==NULL)
        return ERROR;
    LNode* tmp=L->head->next;
    if(tmp==NULL)
        return EMPTY;
    int flag1=0;
    while (tmp!=L->head->next||!flag1){     //Modified
        flag1=1;
        LNode* j=tmp->next;
        while(j!=L->head->next){        //Modified
            if((*compare)(*tmp->data,*j->data)){
//                LNode *Ptmp= PriorPos(*L,tmp),*Jtmp= PriorPos(*L,j),*Jnext=j->next;
//                Ptmp->next=j;
//                Jtmp->next=tmp;
//                j->next=tmp->next;
//                tmp->next=Jnext;
                ElemType *Tdata= tmp->data;
                tmp->data=j->data;
                j->data=Tdata;
            }
            j=j->next;
        }
        tmp=tmp->next;
    }

    return OK;
}

LNode* PriorPosForSelectSort(LinkList L,LNode* p){
    if(L.head==NULL)    return NULL;

    LNode * tmp=L.head->next;
    while (tmp->next!=p&&tmp->next!=L.head->next){      //Modified
        tmp=tmp->next;
    }
    if(tmp==L.tail) return NULL;
    return tmp;
}

Status ListSelectSort(LinkList* L,Status (*compare)(ElemType e,ElemType f)){
    if(L==NULL||L->head==NULL)
        return ERROR;
    if(L->head->next==NULL)
        return EMPTY;

    LNode * r=L->head,*min=L->head->next;

    while (min->next!=L->head->next){        //Modified
        LNode * tmp=r->next;
        int flag=0;
        while (tmp!=L->head->next||!flag){     //Modified
            flag=1;
            if((*compare)(*tmp->data,*min->data)){
                min=tmp;
            }
            tmp=tmp->next;
        }
        LNode *pNext=r->next;

        if(min!=L->tail){
            min->prior->next=min->next;
            min->next->prior=min->prior;
        }      //Modified
        else {
            L->tail = min->prior;
            min->prior->next=min->next;
            min->next->prior=min->prior;
        }
        if(r!=L->head){
            min->prior=r;
        } else
            min->prior=L->tail;
        r->next->prior=min;
        r->next=min;
        L->tail->next=L->head->next;
        min->next=pNext;
        r=min;
        min=r->next;
    }

    return OK;
}


//Status ListRevers(LinkList* L){
//    if(L==NULL||L->head==NULL)  return ERROR;
//
//    L->tail=L->head->next;
//    LNode* Ptmp=L->head->next;
//    LNode *p=NULL,*q;
//    int flag=0;
//    while (Ptmp!=L->head->next||!flag){        //Modified
//        flag=1;
//        q=Ptmp->next;
//        Ptmp->next=p;
//        p=Ptmp;
//        Ptmp=q;
//    }
//    L->head->next=p;
//    L->tail->next=L->head->next;
//    return OK;
//}

Status ListRevers(LinkList* L){
    if(L==NULL||L->head==NULL)  return ERROR;

    LNode* Ptmp=L->head->next,*tmp;
    tmp=Ptmp->prior;
    Ptmp->prior=Ptmp->next;
    Ptmp->next=tmp;

    Ptmp=L->tail;
    tmp=Ptmp->prior;
    Ptmp->prior=Ptmp->next;
    Ptmp->next=tmp;

    Ptmp=L->head->next->prior;
    tmp=L->tail;

    LNode *oldPrior=NULL,*oldNext;//原来为p，q
    while (Ptmp!=tmp){

        oldNext=Ptmp->next;
        oldPrior=Ptmp->prior;
        Ptmp->next=oldPrior;
        Ptmp->prior=oldNext;
        Ptmp=Ptmp->prior;
    }
    tmp=L->head->next;
    L->head->next=L->tail;
    L->tail=tmp;

    return OK;
}



